COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{⊂C<NαCOMPARING.λ30P80I425,0JCFA} SECTION 8.
C00007 00003	⊂8.1 	A Polygon Matching Method.⊃
C00013 00004	⊂8.2	Geometric Normalization of Polygons.⊃
C00017 00005	⊂8.3	Compare by Recursive Windowing.⊃
C00019 00006	⊂8.4	Related Work and Work Yet To Be Done.⊃
C00021 ENDMK
C⊗;
{⊂C;<N;αCOMPARING.;λ30;P80;I425,0;JCFA} SECTION 8.
{JCFD}    IMAGE COMPARING.
{λ10;W250;JAFA}
	8.0	Introduction to Image Comparing.
	8.1 	A Polygon Matching Method.
	8.2	Geometric Normalization of Polygons.
	8.3	Compare by Recursive Windowing.
	8.4	Related Work and Work Yet To Be Done.
{λ30;W0;I950,0;JU;FA}
⊂8.0	Introduction to Image Comparing.⊃

	The  image compare  process  is both  the  <"keystone of  the
arch">  as well as  the <"weakest link  of the  chain">. By comparing
images, the 3-D  modeling and  the 2-D image  processing are  finally
linked,   however  as will  be  apparent the  implementation to  date
demonstates  only  a  small  part of  what  is
possible. In the feedback perception design,  there are three classes
of  compare  operations: verification,    revelation and  recognition
which may  be  applied to  each  of the  three  kinds of  image  data
structures: raster, contour and mosaic.  The verify compare finds the
corresponding  entities  between a  predicted image  and  a perceived
image for  the  sake  of  calibration measurement and  for  the  sake  of
eliminating  already know  features  from further  consideration.
In vision for inductrial machine assembly, calibration measurements suddenly seem
to be the only kind of vision necessary in many factory situations.
The reveal  compare involves  finding the  corresponding entities  in two
percieved images,  so that the location and extent of new objects can
be  solved.  Finally,   the  recognition  compare  involves matching  a
percieved entity with one of a set of prototype entities.

	From the  view  point of  modeling the  lowest level  compare
operation  should somehow  be arranged  to be a  one to  one template
match rather than a multi dimensional statistical discrimination or a
graph isomorphism  test. That is  if the  entities to be  matched are
incommensurate, the model designer censures
the model  that generated  an unrealistic
prediction rather than the pattern matcher which can not  see a vague
resemblance. Clearly this position  should not be taken to an extreme
and the  present system  could be  enhanced by  the inclusion  of  an
appropriate collection  of traditional  pattern matching  techniques.
However,   two  techniques of commensuration  that are  naturally the
responsibility of  a model  builder are  geometric normalization  and
topological   segmentation.      Geometric   normalization   involves
eliminating the irrelevant differences such as location,  orientation
and scale.   Topological segmentation involves subdividing  a complex
object  into pieces,  (perhaps even  canonical pieces)  so  that only
simple small  parts need  be  matched (that  is the  compare  becomes
recursive).   The remainder  of this  chapter explains  a method  for
matching structured  images consisting of polygons. The most original
part of the method  involves finding the correspondence,  illustrated
in figure 8.1,   for polygonal figures that fission  or fuse from one
image to the next.

	FIGURE 8.1	EXAMPLE OF POLYGON FUSION COMPARE.

⊂8.1 	A Polygon Matching Method.⊃

	The image compare  process in CRE, connects the  polygons and
arcs  of one image  with corresponding  polygons and arcs  of another
image. CRE's  compare  solves  the problem  of  correlating  polygons
between two similar images and is composed of four steps: 
{λ10;JA}
   1. Compute polygonal lamina inertia tensors, <lamten nodes>.
   2. Compare and connect polygons one to one at corresponding levels of the nested polygon tree.
   3. Compare and connect polygons two to one at corresponding levels of the nested polygon tree.
   4. Compare and connect vertices of connected polygons using recursive windowing.
{λ30;JU}
	First, the lamina inertia tensor nodes (called <lamten>'s) of
all the  polygons of an image are  computed. A lamten node contains
the center of mass as well as the tensor of a polygon. The meaning
of the  inertia tensor  is that  it characterizes  each polygon  as a
rectangle of  a certain length and width at a particular location and
oriention; and  of further  importance  such inertia  tensors can  be
added to characterize two or more polygons by a single rectangle.  It
is the lamten rectangles that provide a basis for normalization.

	Second, all the lamtens  of the polygons of one  level of the
first image are  compared with all the lamtens of the polygons of the
corresponding level of the second image for nearly exact match.   The
potentially (M*N/2) compares  is avoided by sorting on  the center of
mass  locations.  In CRE,  which  is intended for comparing sequences
of pictures of natural scenes;  match for center of mass  location is
tested  first and  most  strictly,   followed by  match  for inertia.
Pointers between matching polygons are  placed in two link  positions
of the polygon nodes  and the polygons are considered to  be matched.

	Third,  all  the unmated polygons  of a level  are considered
two at  a time and a fusion  lamten node for each pair  is made.  The
potentially (N*N/2-N) fusion lamtens  are avoided because there is  a
maximum possible unmated inertia in the  other image; if there are no
unmated  polygons in one image  then the extra  polygons of the first
image can be ignored. In  the event where there are  unmated polygons
in corresponding  levels of the two images,  the multi-polygon fusion
lamten of one  are compared  with the  single polygon  lamten of  the
other. The fusion (fission) compare solves  the rather nasty problem,
of  linking two contour polygons  of one image with  a single contour
polygon in the next image.

	Fourth, the vertices  of mated polygons are  in turn compared
and  mated.  To start a vertex compare,   the vertices of one polygon
are translated,   rotated and  dilated to  get that polygon's  lamten
rectangle coincidant  with its mate  (or mates).   Conceptually, each
vertex of  one polygon  is compared  with each  vertex of  the  other
polygon(s) and the mutually closest vertices (closer than an epsilon)
are considered to be mated.  Actually the potential (N*M) compares are
avoided by  a recursive  windowing scheme  similar to  that used  in
hidden line elimination algorithms.
The results  of vertex  compare and  mate are  illustrated in
figure 8.2;  the compare execution takes less than a second on images
such as  the pump,   blocks,  and  dolls that appear in  the figure.

FIGURE 8.2	VERTEX MATING - PUMP, BLOCKS and DOLL.
⊂8.2	Geometric Normalization of Polygons.⊃

	The  lamina inertia  tensor  of a  polygon  with N  sides  is
computed by summation over N trapezoids.  The trapezoid corresponding
to each side is formed by dropping perpendiculars <up> to the  top of
the image  frame; each such  trapezoid consists  of a rectangle  an a
right triangle;  since the sides of polygons are directed vectors the
areas  of the  triangles  and  rectangles  can be  arranged  to  take
positive and negative values  such that a summation will describe the
interior region of the polygon as positive.  The equations  necessary
for computing  the lamina inertia  tensor of  a polygon were  derived
from material in Goldstein's Classical Mechanics, [Goldstein].

FIGURE 8.3	LAMTEN TRAPEZOID DECOMPOSITION.

{λ10;JA}
RECTANGLE'S  LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
	MXX	←	B*B*AREA/12;		(B HEIGHT IN ROWS).
	MYY 	←	A*A*AREA/12;		(A WIDTH IN COLUMNS).
	MZZ	←	MXX + MYY;
	PXY 	←	0;

ORIENTED RIGHT TRIANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
	MXX	←	B*B*AREA/18;		(B HEIGHT IN ROWS).
	MYY	←	A*A*AREA/18;		(A WIDTH IN COLUMNS).
	MZZ	←	MXX + MYY;
	PXY	←	-A*B*AREA/36;

SUMMATION OF LAMINA INERTIA TENSORS.
	AREA	←	(AREA1  +  AREA2);
	XCM	←	(AREA1 * XCM1  +  AREA2 * XCM2) / AREA;
	YCM	←	(AREA1 * YCM1  +  AREA2 * YCM2) / AREA;
	MXX	←	MXX1 + YCM1*YCM1*AREA1  +
			MXX2 + YCM2*YCM2*AREA2  -  YCM*YCM*AREA;
	MYY	←	MYY1 + XCM1*XCM1*AREA1  +
			MYY2 + XCM2*XCM2*AREA2  -  XCM*XCM*AREA;
	PXY	←	PXY1 - XCM1*YCM1*AREA1  +
			PXY2 - XCM2*YCM2*AREA2  +  XCM*YCM*AREA;

ANGLE OF PRINCIPLE AXIS
The angle of the principle axis, PHI, lies in the interval -π/2 to π/2.
	PHI	←	0.5*ATAN(2*PXY/(MYY-MXX))
	PXY	←	0.5*(MYY - MXX)*TAN(2*PHI)
TRANSLATION OF LAMINA INERTIA TENSOR AWAY FROM CENTER OF MASS.
	MXX'	←	MXX  +  AREA*DY*DY;
	MYY'	←	MYY  +  AREA*DX*DX;
	PXY'	←	PXY  -  AREA*DX*DY;
ROTATION OF LAMINA INERTIA TENSOR ABOUT CENTER OF MASS.
	C	←	COSINE(PHI);
	S	←	SINE(PHI);
	MXX'	←	C*C*MXX  +  S*S*MYY  -  2*C*S*PXY;
	MYY'	←	C*C*MYY  +  S*S*MXX  +  2*C*S*PXY;
	PXY'	←	(C*C - S*S)*PXY + C*S*(MYY - MXX);
{λ30;JU}

⊂8.3	Compare by Recursive Windowing.⊃

	The final step in  the CRE polygon match (subsection  8.1) is
to   link  the  corresponding  vertices   between  two  geometrically
normalized polygons (or  sets of polygons)  using a nearest  neighbor
criterion. The  nearest neighbors  are found by  recursive windowing,
intially  all the vertices are pushed into  one large window which is
subseqently split until there  were few enough vertices  contained in
the  window to  allow exhautive  comparing.   To make  this windowing
technique applicable  to  the  nearest neighbor  problem  a  distance
criterion, <delta>, has to be declared so that the windows overlap by
that  amount.    Consequently  the  windows  are no  longer  disjoint
rectangles, but are rather boxes with rounded corners,   the smallest
possible window being  a circle with radius, <delta>.   The recursive
windowing  technique is essentially a two dimensional partition sort,
the  technique can  be  generalized  for comparing  edges  and  other
entities in 2-D or higher dimensions.

⊂8.4	Related Work and Work Yet To Be Done.⊃

	To complete the visual feedback system,  there remains yet to
be written an image  compare that uses both raster based and polygon based
techniques. The  two kinds  of  compares are  symbiotic in  that  the
polygon compare could aim the  raster correlator alleviating the need
to  do bulk  correlation over wide  areas, and  the raster correlator
could verify  and  improve the  measurement  of corresponding  vertex
loci.  At Stanford, image comparison by raster correlation techniques
is begin worked on by [Quam],  Hannah and Morevac.  Another  approach
to comparing polygons is to examine their curvature, the curvature of
a  polygon can be expressed  as a parametric function  of arc length;
two such  functions can be  normalized and  alligned and  differenced
using statistical techniques [Zahn].